"""
队列和堆栈
问题
给定一个数字字符串，返回该数字可能表示的所有字母组合。
数字到字母的映射（就像电话按键上的一样）
如下所示。
输入：数字字符串 “23”
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。

这题其实含义是是枚举所有可能的组合方式。如果题目要求是枚举“23”的所有可能字母组合，我们很好做，2重循环对吧？但是现在难就难在，一开始你不知道输入是什么，你没办法确定组合长度，组合个数，也没办法确定循环层数，这时候怎么办？？？

这里有两个思路，也是很常用的思路：递归，队列。

思路1：递归
递归一般是解决一些整体不好求的问题。它通过把大问题划小，然后找到一种特定的规律，然后求解。

递归的思路我们很好理解，我们没办法确定整体，我可以先从入手。

假定有个数字串“23456”

假定除了数字’2’的组合已经求出来了，准备求’3’，那我只要把‘3’所代表的’def’加到之前字符串他们每一个的后面就好。
假定除了数字’2’的组合已经求出来了，准备求’4’，那我只要把‘4’所代表的’hij’加到之前字符串他们每一个的后面就好。
……
一直这样推下去，直到发现6’后面是空的了，那将当前这个字符串加入列表就好了。

以下是基于此问题的分析和解决方案：
问题分析
输入是一个数字字符串，每个数字对应特定的字母集合（例如：2 -> 'abc', 3 -> 'def'）。
需要枚举所有可能的组合，这可以通过递归或迭代方法实现。
组合数量取决于输入字符串长度，循环层数无法提前确定，因此需要动态处理。

解决方案
方法一：队列（BFS）
通过使用队列的方式可以按层扩展生成所有组合：
初始化一个队列，并将第一个数字对应的字母依次入队。
每次取出队首元素，并在该元素基础上加上下一个数字对应的字母，重新入队。
直到队列中所有元素长度等于输入数字字符串的长度，即为最终的所有组合。

原理说明
使用 deque 实现一个队列，初始时队列中有一个空字符串 ""，表示起始路径。
每次取出队列中的元素，并在其基础上添加当前数字对应的每一个字母，然后重新入队。
这个过程相当于一层一层地扩展组合，直到处理完所有输入数字。
最终队列中的所有元素就是所有可能的字母组合。

方法二：递归（DFS）
递归方法更直观，适合深度优先探索每一种可能性：
定义递归函数 dfs(index, path)，其中 index 表示当前处理的数字位置，path 是已经构建的字母路径。
当 path 的长度等于输入字符串长度时，将其加入结果集。
否则，遍历当前数字对应的所有字母，递归调用处理下一个数字。

BFS（广度优先搜索）和 DFS（深度优先搜索）是两种常用的遍历或搜索图/树结构的算法策略。在解决数字字符串生成字母组合的问题中，它们体现了不同的思路和实现方式。

---

## 🧠 BFS 和 DFS 的核心区别

| 特性 | **BFS (广度优先搜索)** | **DFS (深度优先搜索)** |
|------|-------------------------|-------------------------|
| **探索顺序** | 按层进行扩展，先访问当前节点的所有邻居，再深入下一层 | 一直深入到底，直到不能再深入为止，然后回溯 |
| **数据结构** | 使用 `队列`（FIFO：先进先出） | 使用 `栈` 或递归（系统调用栈） |
| **适用场景** | 寻找最短路径、按层处理、组合问题等 | 路径探索、状态空间搜索、组合问题等 |
| **内存消耗** | 空间复杂度通常较高（保存所有层的节点） | 空间复杂度较低（只保存当前路径） |
| **实现难度** | 需要维护队列，逻辑稍复杂 | 递归实现简洁直观，但容易栈溢出 |

---

## 🔍 在本题中的实现原理对比

### ✅ BFS 实现原理（使用队列）

#### 思路：
- 初始化一个队列，放入空字符串 `""`，表示起始路径。
- 对每个输入的数字字符，依次取出队列中的每一个已有路径，并与该数字对应的所有字母进行拼接，形成新的路径，重新入队。
- 每轮处理一个数字字符，直到处理完所有字符。
- 最终队列中的所有字符串就是所有可能的字母组合。

#### 示例流程（输入 `"23"`）：

1. 初始队列: `[""]`
2. 处理 `'2'`（对应 `'abc'`）:
   - 取出 `""`，添加 `'a'`, `'b'`, `'c'` → 队列变为 `['a', 'b', 'c']`
3. 处理 `'3'`（对应 `'def'`）:
   - 取出 `'a'`，添加 `'d'`, `'e'`, `'f'` → `['b', 'c', 'ad', 'ae', 'af']`
   - 取出 `'b'`，添加 `'d'`, `'e'`, `'f'` → `['c', 'ad', 'ae', 'af', 'bd', 'be', 'bf']`
   - 取出 `'c'`，添加 `'d'`, `'e'`, `'f'` → `['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']`
4. 返回结果：`['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']`

#### 优点：
- 明确的层次结构
- 不依赖递归，避免栈溢出

---

### ✅ DFS 实现原理（使用递归）

#### 思路：
- 定义递归函数 `dfs(index, path)`，其中：
  - `index` 表示当前处理到第几个数字字符
  - `path` 表示已经构建好的字母路径
- 当 `index == len(digits)` 时，说明已经构建完成一个完整组合，加入结果列表。
- 否则，遍历当前数字对应的所有字母，递归地继续构建下一个字符的路径。

#### 示例流程（输入 `"23"`）：

1. 从 `index=0` 开始，`digits[0] = '2'`，对应 `'abc'`
2. 分别尝试 `'a'`, `'b'`, `'c'`：
   - `'a'` → `index=1`，`digits[1] = '3'`，对应 `'def'`
     - `'a' + 'd'` → 加入结果
     - `'a' + 'e'` → 加入结果
     - `'a' + 'f'` → 加入结果
   - `'b'` → 同上
   - `'c'` → 同上
3. 最终得到所有 9 种组合。

#### 优点：
- 代码更简洁清晰
- 更符合人类对“穷举”的直觉理解

---

## 📊 时间与空间复杂度比较

| 指标 | **BFS** | **DFS** |
|------|---------|---------|
| **时间复杂度** | O(3^N × 4^M)（N 是 3 字母数字个数，M 是 4 字母数字个数） | O(3^N × 4^M) |
| **空间复杂度** | O(3^N × 4^M)（存储所有中间组合） | O(N)（递归栈深度）+ O(3^N × 4^M)（结果存储） |

> N 为 digits 的长度

---

## ✅ 总结

| 场景 | 推荐方法 |
|------|-----------|
| 输入较长，担心递归栈溢出 | BFS |
| 希望代码简洁，逻辑清晰 | DFS |
| 需要逐层构造组合，如动态规划类问题 | BFS |
| 需要回溯、剪枝操作 | DFS（更灵活） |

在本题中，两者都能正确解决问题，选择取决于具体需求和偏好。BFS 更适合迭代实现，DFS 更适合递归实现。
"""
from sqlalchemy.sql.functions import current_date


class Solution:
    """
    本类提供了一个方法来生成电话号码的字母组合。
    电话号码的每个数字对应着一些字母，这种方法可以找到所有可能的字母组合。
    """

    def letter_combinations_dfs(self, digits: str):
        """
        生成给定数字字符串的所有可能的字母组合。

        参数:
        digits: str - 输入的数字字符串，代表电话号码。

        返回:
        list - 包含所有可能的字母组合的列表。
        """
        # 如果输入为空，直接返回空列表
        if not digits:
            return []

        # 电话号码与字母的映射关系
        phone_map = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }

        # 存储最终的结果
        result = []

        def dfs(index, path):
            """
            深度优先搜索函数，用于生成所有可能的字母组合。

            参数:
            index: int - 当前处理的数字索引。
            path: str - 当前已经生成的字母组合。
            """
            # 如果当前索引等于输入长度，说明已经生成了一个完整的组合
            if index == len(digits):
                result.append(path)
                return

            # 获取当前数字对应的所有可能字母
            possible_letters = phone_map[digits[index]]

            # 遍历当前数字对应的所有字母，尝试添加到当前路径中
            for letter in possible_letters:
                dfs(index + 1, path + letter)

        # 从第一个数字开始递归搜索
        dfs(0, "")
        return result

    def letter_combinations(self, digits: str):
        """
        生成给定数字字符串的所有可能的字母组合。

        参数:
        digits: str - 输入的数字字符串，代表电话号码。

        返回:
        list - 包含所有可能的字母组合的列表。
        """
        # 如果输入为空，则直接返回空列表
        if not digits:
            return []

        # 数字到字母的映射，对应电话键盘上的数字
        phone_map = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }

        # 使用队列来存储当前生成的所有组合
        from collections import deque
        queue = deque([""])

        # 遍历输入的每个数字字符
        for i in range(len(digits)):
            current_digit = digits[i]
            # 获取当前数字字符对应的字母
            letters = phone_map[current_digit]

            # 记录当前层的队列大小，以便后续迭代
            level_size = len(queue)
            # 遍历当前层的队列中的每个路径
            for _ in range(level_size):
                # 弹出队列中的当前路径
                path = queue.popleft()

                # 将当前路径与每个可能的字母组合后，加入队列
                for letter in letters:
                    queue.append(path + letter)

        # 最终队列中的内容即为所有可能的字母组合，将其转换为列表返回
        return list(queue)




if __name__ == '__main__':
    solution = Solution()
    print(solution.letter_combinations_dfs("23"))